package com.datastructure.backtrack;

/**
 * @author: 临晖
 * @date: 2023/10/31
 * @description:
 */


import com.sun.org.apache.bcel.internal.generic.NEW;
import com.sun.org.apache.xpath.internal.SourceTree;
import com.sun.org.apache.xpath.internal.functions.FuncStringLength;

import javax.lang.model.element.VariableElement;
import java.sql.Array;
import java.util.*;
import java.util.concurrent.CountDownLatch;

/**
 * 回溯
 */
public class Solution {




    //void backtracking(参数) {
    //    if (终止条件) {
    //        存放结果;
    //        return;
    //    }
    //
    //    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
    //        处理节点;
    //        backtracking(路径，选择列表); // 递归
    //        回溯，撤销处理结果
    //    }
    //}


    //private List<List<Integer>> res = new ArrayList<>();
    //private List<Integer> path = new ArrayList<>();
    ///**
    // * 77. 组合
    // * 中等
    // * 1.5K
    // * 相关企业
    // * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
    // * 你可以按 任何顺序 返回答案。
    // *
    // * @param n
    // * @param k
    // * @return
    // */
    //public List<List<Integer>> combine(int n, int k) {
    //    backtracking(n, k, 1);
    //    return res;
    //}
    //
    //public void backtracking(int n, int k, int startIndex) {
    //
    //    if (path.size() == k) {
    //        res.add(new ArrayList<>(path));
    //        return;
    //    }
    //
    //    for (int i = startIndex; i <= n; i++) {
    //        path.add(i);
    //        backtracking(n, k, i + 1);
    //        path.remove(path.size() - 1);
    //    }
    //}
    //
    //
    ///**
    // *
    // * 216. 组合总和 III
    // * 中等
    // * 774
    // * 相关企业
    // * 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
    // * 只使用数字1到9
    // * 每个数字 最多使用一次
    // * 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
    // *
    // * @param k
    // * @param n
    // * @return
    // */
    //
    //public List<List<Integer>> combinationSum3(int k, int n) {
    //    combination(k, n, 1);
    //    return res;
    //}
    //
    //
    //public void combination(int k, int n, int startIndex) {
    //    //递归退出条件
    //    if (path.size() == k) {
    //
    //        int sum = 0;
    //        for (int i = 0; i < path.size(); i++) {
    //            sum += path.get(i);
    //        }
    //
    //        if (sum == n) {
    //            res.add(new ArrayList<>(path));
    //        }
    //
    //        return;
    //    }
    //    //递归体
    //
    //    for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
    //        path.add(i);
    //        combination(k, n, i + 1);
    //        path.remove(path.size() - 1);       //回溯
    //    }
    //
    //    //返回
    //    //return;
    //
    //}
    //
    //
    ///**
    // * 17. 电话号码的字母组合
    // * 中等
    // * 2.7K
    // * 相关企业
    // * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
    // * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
    // * @param digits
    // * @return
    // */
    //private List<String> strs = new ArrayList<>();
    //public List<String> letterCombinations(String digits) {
    //    if (digits == null || "".equals(digits)) {
    //        return strs;
    //    }
    //    String[] str = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    //    letter("", digits, 0, str);
    //    return strs;
    //
    //}
    //
    //
    //
    //public void letter(String str, String digits, int count, String[] strArray) {
    //    if (count == digits.length()) {
    //        strs.add(str);
    //        return;
    //    }
    //
    //    //递归体
    //    String s = strArray[digits.charAt(count) - '0'];
    //    for (int i = 0; i < s.length(); i++) {
    //        str += s.charAt(i);
    //        letter(str, digits, count + 1, strArray);
    //        str = str.substring(0, str.length() - 1);
    //    }
    //}
    //
    //
    ///**
    // * 39. 组合总和
    // * 中等
    // * 2.7K
    // * 相关企业
    // * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
    // * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
    // * 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
    // *
    // *
    // * @param candidates
    // * @param target
    // * @return
    // */
    //public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    //    Arrays.sort(candidates);
    //    combination(candidates, target, 0, 0);
    //    return res;
    //}
    //
    //
    //public void combination(int[] candidates, int target, int sum, int index) {
    //    //递归退出条件
    //    if (sum > target) {
    //        return;
    //    }
    //
    //    if (sum == target) {
    //        res.add(new ArrayList<>(path));
    //        return;
    //    }
    //
    //
    //    //递归体
    //    for (int i = index; i < candidates.length; i++) {
    //
    //        if (i > index && candidates[i] == candidates[i - 1]) {          //这里表示，去除重复答案
    //            continue;
    //        }
    //        sum += candidates[i];
    //
    //        if (sum > target) {
    //            return;
    //        }
    //
    //        path.add(candidates[i]);
    //        combination(candidates, target, sum, i + 1);        //i + 1，表示去重，数组中一个元素只能使用一次
    //        path.remove(path.size() - 1);       //回溯
    //        sum -= candidates[i];
    //
    //
    //    }
    //
    //    //返回
    //}
    //
    //
    ///**
    // * 131. 分割回文串
    // * 中等
    // * 1.7K
    // * 相关企业
    // * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
    // * 回文串 是正着读和反着读都一样的字符串。
    // *
    // *
    // * 该题换一种问法：
    // * 给定一个字符串，问，该字符串可以分割出几个回文
    // *
    // * @param s
    // * @return
    // */
    //public List<List<String>> partition(String s) {
    //    ArrayList<List<String>> res = new ArrayList<>();
    //    ArrayList<String> list = new ArrayList<>();
    //    par(res, list, s, 0);
    //    return res;
    //}
    //
    ////判断是否为回文字符串
    //public boolean isPalindrome(String str) {
    //    int preIndex = 0;
    //    int lastIndex = str.length() - 1;
    //
    //    while (preIndex <= lastIndex) {
    //        if (str.charAt(preIndex) != str.charAt(lastIndex)) {
    //            return false;
    //        }
    //        preIndex++;
    //        lastIndex--;
    //    }
    //
    //    return true;
    //}
    //
    //public void par(List<List<String>> lists, List<String> list, String s, int startIndex) {
    //    if (startIndex >= s.length()) {
    //        lists.add(new ArrayList<>(list));
    //        return;
    //    }
    //
    //    //
    //    for (int i = startIndex; i < s.length(); i++) {
    //
    //        String s1 = s.substring(startIndex, i+ 1);
    //        //判断是否为回文
    //        boolean flag = isPalindrome(s1);
    //        if ( flag ) {               //如果该字符串是回文的话，那么继续分割下去
    //            list.add(s1);
    //        } else {
    //            continue;           //如果该字符串不是回文的话，那么重新开始分割
    //        }
    //
    //        //递归
    //        par(lists, list, s, i + 1);
    //
    //        list.remove(list.size() - 1);
    //
    //
    //
    //    }
    //
    //}
    //
    //
    ///**
    // * 93. 复原 IP 地址
    // * 中等
    // * 1.3K
    // * 相关企业
    // * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
    // * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
    // * 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
    // * @param s
    // * @return
    // */
    //public List<String> restoreIpAddresses(String s) {
    //    ArrayList<String> res = new ArrayList<>();
    //    if (s.length() > 12 || s.length() < 12) {
    //
    //    }
    //    restoreIp(res, s, 0, 0);
    //    return res;
    //}
    //
    //public void restoreIp(List<String> res, String s, int startIndex, int pointNum) {
    //    if (pointNum >= 3) {
    //        if (isValid(s, startIndex, s.length() - 1)) {
    //            res.add(s);
    //        }
    //        return;
    //    }
    //
    //
    //    for (int i = startIndex; i < s.length(); i++) {
    //        if (isValid( s, startIndex, i)) {
    //            s = s.substring(0, i + 1) + "." + s.substring(i + 1);
    //            pointNum++;
    //            restoreIp(res, s, i + 2, pointNum);
    //            pointNum--;         //回溯
    //            s = s.substring(0, i + 1) + s.substring(i + 2);
    //        } else {
    //            //不符合当前要求的情况：
    //            //1.首位为0
    //            //2.值大于255
    //            //3.大于三位
    //            //如果继续往后，依然也不符合要求，所以这里直接break，而不是continue
    //            break;
    //        }
    //
    //
    //
    //
    //    }
    //}
    //
    //// 判断字符串s在左闭⼜闭区间[start, end]所组成的数字是否合法
    //private Boolean isValid(String s, int start, int end) {
    //    if (start > end) {
    //        return false;
    //    }
    //    if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法
    //        return false;
    //    }
    //    int num = 0;
    //    for (int i = start; i <= end; i++) {
    //        if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到⾮数字字符不合法
    //            return false;
    //        }
    //        num = num * 10 + (s.charAt(i) - '0');
    //        if (num > 255) { // 如果⼤于255了不合法
    //            return false;
    //        }
    //    }
    //    return true;
    //}
    //
    //
    ///**
    // * 78. 子集
    // * 中等
    // * 2.2K
    // * 相关企业
    // * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
    // *
    // * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
    // * 示例 1：
    // *
    // * 输入：nums = [1,2,3]
    // * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
    // * 示例 2：
    // *
    // * 输入：nums = [0]
    // * 输出：[[],[0]]
    // * @param nums
    // * @return
    // */
    //public List<List<Integer>> subsets(int[] nums) {
    //    subset(nums, 0);
    //    res.add(new ArrayList<>());
    //    return res;
    //}
    //
    //
    //public void subset(int[] nums, int startIndex) {
    //    //退出条件
    //    if (startIndex >= nums.length) {
    //        return;
    //    }
    //
    //    //递归体
    //    for (int i = startIndex; i < nums.length; i++) {
    //        path.add(nums[i]);
    //        res.add(new ArrayList<>(path));
    //        subset(nums, i + 1);
    //        path.remove(path.size() - 1);
    //    }
    //}
    //
    //
    ///**
    // * 90. 子集 II
    // * 中等
    // * 1.2K
    // * 相关企业
    // * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
    // *
    // * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
    // *
    // *
    // *
    // * 示例 1：
    // *
    // * 输入：nums = [1,2,2]
    // * 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
    // * 示例 2：
    // *
    // * 输入：nums = [0]
    // * 输出：[[],[0]]
    // * @param nums
    // * @return
    // */
    //public List<List<Integer>> subsetsWithDup(int[] nums) {
    //    Arrays.sort(nums);
    //    subsetsWith(nums, 0);
    //    res.add(new ArrayList<>());
    //    return res;
    //}
    //
    //
    //public void subsetsWith(int[] nums, int startIndex) {
    //    if (startIndex >= nums.length) {
    //        return;
    //    }
    //
    //    //递归
    //    for (int i = startIndex; i < nums.length; i++) {
    //
    //        if (i > startIndex && nums[i] == nums[i - 1])  {
    //            continue;
    //        }
    //
    //        path.add(nums[i]);
    //        res.add(new ArrayList<>(path));
    //        subsetsWith(nums, i + 1);
    //        path.remove(path.size() - 1);
    //    }
    //}
    //
    //
    ///**
    // *
    // * 491. 递增子序列
    // * 中等
    // * 739
    // * 相关企业
    // * 给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
    // *
    // * 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
    // *
    // *
    // *
    // * 示例 1：
    // *
    // * 输入：nums = [4,6,7,7]
    // * 输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
    // * 示例 2：
    // *
    // * 输入：nums = [4,4,3,2,1]
    // * 输出：[[4,4]]
    // *
    // * @param nums
    // * @return
    // */
    //
    //public List<List<Integer>> findSubsequences(int[] nums) {
    //    findSubsequ(nums, 0);
    //    return res;
    //}
    //
    //public void findSubsequ(int[] nums, int startIndex) {
    //    //循环退出条件
    //    if (startIndex >= nums.length) {
    //        return;
    //    }
    //    //
    //    HashMap<Integer, Boolean> map = new HashMap<>();
    //    for (int i = startIndex; i < nums.length; i++) {
    //        Boolean flag = map.getOrDefault(nums[i], false);
    //        if (!flag) {                    //数层去重
    //            map.put(nums[i], true);     //设置为true
    //            if (path.size() != 0 && nums[i] < path.get(path.size() - 1)) {      //递增序列
    //                continue;
    //            }
    //
    //            path.add(nums[i]);
    //            if (path.size() >= 2) {         //必须要大于等于2
    //                res.add(new ArrayList<>(path));
    //            }
    //
    //            findSubsequ(nums, i + 1);
    //
    //            path.remove(path.size() - 1);
    //
    //
    //        }
    //    }
    //}
    //
    //
    ///**
    // * 46. 全排列
    // * 中等
    // * 2.7K
    // * 相关企业
    // * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
    // *
    // *
    // *
    // * 示例 1：
    // *
    // * 输入：nums = [1,2,3]
    // * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    // * 示例 2：
    // *
    // * 输入：nums = [0,1]
    // * 输出：[[0,1],[1,0]]
    // * 示例 3：
    // *
    // * 输入：nums = [1]
    // * 输出：[[1]]
    // * @param nums
    // * @return
    // */
    //public List<List<Integer>> permute(int[] nums) {
    //    //Arrays.sort(nums);        //涉及到去重
    //    permut(nums);
    //    return res;
    //}
    //
    //public void permut(int[] nums) {
    //    if (path.size() == nums.length) {
    //        res.add(new ArrayList<>(path));
    //        return;
    //    }
    //
    //    for (int i = 0; i < nums.length; i++) {
    //        //if (nums[i] == -11 || (i > 0 && nums[i] == nums[i - 1])) {
    //        //    continue;
    //        //}
    //        if (nums[i] == -11) {
    //            continue;
    //        }
    //        path.add(nums[i]);
    //        int temp = nums[i];
    //        nums[i] = -11;
    //        permut(nums);
    //        path.remove(path.size() - 1);
    //        nums[i] = temp;
    //    }
    //}
    //

    /**
     * 332. 重新安排行程
     * 困难
     * 855
     * 相关企业
     * 给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
     * 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
     * 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
     * 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
     *
     * @param tickets
     * @return
     */

    //private LinkedList<String> path = new LinkedList<>();
    //private Map<String, Map<String, Integer>> map = new HashMap<>();        //<出发地, (<到达地, 机票次数>,<到达地2, 机票次数>,<..., ....>, ...>
    //public List<String> findItinerary(List<List<String>> tickets) {
    //    for (List<String> ticket : tickets) {
    //        Map<String, Integer> temp;
    //        if (map.containsKey(ticket.get(0))) {
    //            temp = map.get(ticket.get(0));
    //            temp.put(ticket.get(1), temp.getOrDefault(ticket.get(1), 0) + 1);
    //        } else {
    //            temp = new TreeMap<>();         //底层红黑树，直接排序
    //            temp.put(ticket.get(1), 1);
    //        }
    //        map.put(ticket.get(0), temp);
    //    }
    //
    //    path.add("JFK");
    //    backTracking(tickets.size());
    //    return path;
    //}
    //
    //public boolean backTracking(int num) {
    //    if (path.size() == num + 1) {
    //        return true;
    //    }
    //    String last = path.getLast();
    //    if (map.containsKey(last)) {            //如果，没有对应的去的地方，直接false
    //        for (Map.Entry<String, Integer> target : map.get(last).entrySet()) {
    //            Integer count = target.getValue();
    //            if (count > 0) {            //机票没有用还
    //                path.add(target.getKey());
    //                target.setValue(count - 1);
    //                if (backTracking(num)) {
    //                    return true;
    //                }
    //                target.setValue(count);     //回溯
    //                path.removeLast();
    //            }
    //
    //        }
    //    }
    //
    //    return false;
    //
    //}


    /**
     * 51. N 皇后
     * 困难
     * 2K
     * 相关企业
     * 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
     * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
     * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
     * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
     * @param n
     * @return
     */

    //private List<List<String>> ress = new ArrayList<>();
    //public List<List<String>> solveNQueens(int n) {
    //    ArrayList<Integer> res = new ArrayList<>();
    //    sloveNQueen(res, n);
    //    return ress;
    //}
    //
    //
    //public void  sloveNQueen(List<Integer> res, int n) {
    //    if (res.size() == n) {
    //        ArrayList<String> list = new ArrayList<>();
    //        for (int i = 0; i < res.size(); i++) {
    //            String str = "";
    //            for (int j = 0; j < res.size(); j++) {
    //
    //                if (j == res.get(i)) {
    //                    str += "Q";
    //                } else {
    //                    str += ".";
    //                }
    //
    //            }
    //            list.add(str);
    //
    //        }
    //        ress.add(list);
    //        return;
    //    }
    //
    //    for (int i = 0; i < n; i++) {           //列
    //        res.add(i);
    //        if (judge(res, res.size() - 1)){
    //            sloveNQueen(res, n);
    //        }
    //
    //        res.remove(res.size() - 1);
    //
    //    }
    //
    //
    //}
    //
    //public boolean judge(List<Integer> res, int n) {
    //    for (int i = 0; i < n; i++) {           //代表行
    //        if (res.get(i) == (int)res.get(n) || Math.abs(n - i) == Math.abs(res.get(n) - res.get(i))) {
    //            return false;
    //        }
    //    }
    //    return true;
    //}


    public void solveSudoku(char[][] board) {
        solveSudokuHelper(board);
    }

    private boolean solveSudokuHelper(char[][] board){
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] != '.') {
                    continue;
                }

                for (char k = '1'; k  <= '9'; k++) {
                    if (isValidSudoku(i, j, k, board)) {
                        board[i][j] = k;
                        if (solveSudokuHelper(board)) {
                            return true;
                        }
                        board[i][j] = '.';
                    }

                }
                return false;
            }
        }
        return false;
    }

    /**
     * 判断棋盘是否合法有如下三个维度:
     *     同行是否重复
     *     同列是否重复
     *     9宫格里是否重复
     */
    private boolean isValidSudoku(int row, int col, char val, char[][] board){
        // 同行是否重复
        for (int i = 0; i < 9; i++){
            if (board[row][i] == val){
                return false;
            }
        }
        // 同列是否重复
        for (int j = 0; j < 9; j++){
            if (board[j][col] == val){
                return false;
            }
        }
        // 9宫格里是否重复
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++){
            for (int j = startCol; j < startCol + 3; j++){
                if (board[i][j] == val){
                    return false;
                }
            }
        }
        return true;
    }





    public static void main(String[] args) {
        Integer[] ans = {1, 4, 2, 3};
        Arrays.sort(ans, (o1, o2) ->{
            return o2 - o1;
        });
        for (int num : ans) {
            System.out.println(num);
        }

    }



}
